Complex systems are all around us, including such examples as highway and air traffic systems; telephone networks; financial and banking systems; systems for the manufacture, distribution and sale of retail goods; legal systems; computer systems of various types; information transmission networks; and many more. In large part, these systems are characterized by concurrency (i.e., a number of actions may be occurring at the same time) and by asynchronicity (i.e., there is no master clock controlling the timing of events; many events can occur independently of one another). The development, modification and management of such systems is a very expensive, time-consuming and difficult task. Because of these and other factors, considerable efforts have been devoted over recent years to developing ways to analyze, simulate and (in some cases) control such systems. For example, one would like to be able to know, analytically, whether a change proposed for the structure or control programs for the long-distance telephone network is safe, or if it will cause the system to become deadlocked under some set of circumstances; it is undesirable to simply wait to see if something disastrous is going to happen.
Computer-graphical methods are being used more and more frequently in the specification and design of complex systems. The resulting models provide a basis for validating the design concepts, because they can be understood both by the designer and by the user, and because they can be scrutinized to determine whether the user's requirements have been satisfied. The model can then be used as a guide to, or vehicle for, the implementation or control of the actual physical system. For example, a computer program implementing the model can be used to control the system operation. The system might, thus, be a telephone switching network and the program might operate the digital controller which, in turn, operates the switches. Or the system might be a subway traffic control system and the program might operate signal lights, dispatch scheduling, and so forth.
Executable models of complex systems (i.e., computer programs which model these systems) are now being introduced into practice. In general, they may be classified into two categories: (1) models based on an underlying mathematical framework and (2) models based on an ad hoc graphical representation tied to conventional programming languages. Both types of models can be executed and, in that sense, can be thought of as programs. Models of the first type, moreover, can be analyzed according to certain rules, to discover whether the system possesses certain behavioral properties. These properties include deadlock, safety, and some forms of invariance. Performance analysis is also possible in some cases.
Few, if any, techniques exist for effectively marrying the two categories of executable models. Thus, one does not readily obtain a model which is both graphically represented or constructed and which is also analyzable. One graphical approach which has been developed for modelling and simulating systems exhibiting concurrency and asynchronicity is that of Petri nets. One reason Petri net representations are used is that they are also somewhat analyzable. A good discussion of the history and general principles of Petri nets is contained in T. Murata, "Petri Nets: Properties, Analysis and Applications," Proceedings of the IEEE, Vol. 77, No. 4, April 1989 (New York) at 541-580, and T. Agerwala, "Putting Petri Nets to Work," Computer, Vol. 12, No. 12, Dec. 1979, at 85-94, both of which are hereby incorporated by reference. Though Petri nets have been very useful for modelling systems graphically and mathematically, and though theoretically they are useful for system analysis, as well, it has been found that there is a tradeoff between modeling generality and analysis capability. That is, the more general the model represented by the Petri net, the less amenable it is to analysis. Indeed, it has been said that the complexity problem is a major weakness of Petri nets; that is, Petri-net-based models become too large for analysis even for a modest size system. Moreover, Petri net models and models based on other such paradigms typically are not analyzable, though they are developed on sophisticated computer systems. Thus, they do not address details of behavior of the complex system which they model. In other words, they do not reveal properties of the modelled system, they only simulate it. Validation that the system behaves as desired occurs only by observing the actual operation of the system. Consequently, serious design flaws and performance limitations may not be discovered until the system is in use. Correction of these conditions can be very costly and time-consuming, to say the least. At least one hardware system has been proposed for implementing Petri net models. See U.S. Pat. No. 4,700,187, titled Programmable, Asynchronous Logic Cell and Array, issued Oct. 13, 1987 in the name of Frederick C. Furtek. Though this system permits simulation of Petri nets as, essentially, executable models, it still does not analyze system properties.
Accordingly, it is an object of the invention to provide an improved method for modelling complex systems.
It is another object to provide a method for generating executable models of complex systems.
Still another object of the invention is to provide a method for generating executable models of large complex systems from simpler models of parts of the system, i.e., subsystems.
Yet another object of the invention is to generate models of complex systems which are analyzable, to permit detection of predetermined system behaviors or properties.
A further object of the invention is to provide a method for graphically constructing executable models of systems, which are also analyzable.